package algorithm;

/**
 * 110. 平衡二叉树
 * @author Panbo Guo
 * @date 2021/7/15
 */
public class T00110 {

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{1,2,3,4,null,6,5};
        System.out.println(new Solution().isBalanced(TreeUtils.buildTree(arr)));
    }

    static class Solution {
        public boolean isBalanced(TreeNode root) {
            if (root == null) return true;
            return Math.abs(maxHeight(root.left) - maxHeight(root.right)) <= 1
                    && isBalanced(root.left) && isBalanced(root.right);
        }

        private int maxHeight(TreeNode root) {
            if (root == null) return 0;
            return Math.max(maxHeight(root.left), maxHeight(root.right)) + 1;
        }
    }
}
